package listbyorder.access001_100.test72;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/4 8:38
 */
public class Solution2 {

    // 方法二： 暴力递归改动态规划
    public int minDistance(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        for (int i = len1; i >= 0; i--) {
            for (int j = len2; j >= 0; j--) {
                if (i == len1) {
                    dp[i][j] = len2 - j;
                } else if (j == len2) {
                    dp[i][j] = len1 - i;
                } else if (word1.charAt(i) == word2.charAt(j)) {
                    dp[i][j] = dp[i + 1][j + 1];
                } else {
                    dp[i][j] = 1 + Math.min(Math.min(dp[i + 1][j], dp[i][j + 1]), dp[i + 1][j + 1]);
                }
            }
        }
        return dp[0][0];
    }


    private int getAns(String word1, int s1, int e1, String word2, int s2, int e2) {
        if (s1 == e1) return e2 - s2;
        if (s2 == e2) return e1 - s1;
        if (word1.charAt(s1) == word2.charAt(s2)) {
            return getAns(word1, s1 + 1, e1, word2, s2 + 1, e2);
        } else {
            return 1 + Math.min(
                    Math.min(getAns(word1, s1 + 1, e1, word2, s2, e2), getAns(word1, s1, e1, word2, s2 + 1, e2)),
                    getAns(word1, s1 + 1, e1, word2, s2 + 1, e2));
        }
    }

}
